import org.junit.jupiter.api.Test;

/**
 * 汉诺塔：分治 + 递归
 */
public class TestHanoi {

    /**
     * A，B，C：桩名称
     * 形象记忆：将盘子想象成上下两部分，一部为最下层的一个盘子，一部为由剩余盘子组成的整体，于是问题被简化成了：
     *   1.第一步：【上部】从【起始桩】移动到【辅助桩】，递归
     *   2.第二步：【下部】从【起始桩】移动到【目标桩】
     *   3.第三步：【上部】从【辅助桩】移动到【目标柱】，递归
     */
    @Test
    public void test01() {
        hano(4, "A", "B", "C");
    }

    /**
     * i：盘子层数
     * from：起始桩
     * to：目标桩
     * other：辅助桩
     */
    public void hano (int i, String from, String to, String other) {
        // 基本情形
        if (i == 0) {
            return;
        }

        // 递归情形
        hano(i - 1, from, other, to);
        System.out.printf("%d：%s -> %s%n", i, from, to);
        hano(i - 1, other, to, from);
    }
}
